package org.leetcode.middle.leetcode152;

public class Solution {
    public int maxProduct(int[] nums) {
        int n = nums.length;

        int max =nums[0];

        int [] maxDp = new int[n];
        int [] minDp = new int[n];
        maxDp[0]=nums[0];
        minDp[0]=nums[0];

        for (int i = 1; i < n; i++) {
            maxDp[i]=Math.max(nums[i],Math.max(nums[i]*maxDp[i-1],nums[i]*minDp[i-1]));
            minDp[i]=Math.min(nums[i],Math.min(nums[i]*maxDp[i-1],nums[i]*minDp[i-1]));
            max=Math.max(max,maxDp[i]);
        }

        return max;
    }
}
